import java.util.Arrays;
import java.util.Random;

public class test {
    public static void paixu1(int arr[]){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
                else {
                    break;
                }
            }
        }
    }
    public static void paixu2(int arr[]){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }
                else {
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    public static void haset(int arr[]) {
        int gap = arr.length;
        while (gap >1) {
            gap /= 2;
            hpa(arr,gap);
        }
    }
    public  static void hpa(int arr[],int gap){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }
                else {
                    break;
                }
            }
            arr[j+gap]=temp;
        }
    }

    public static void main(String[] args) {
        int []arr1={5,6,4,2,7,9,1,2};
        paixu1(arr1);
        System.out.println(Arrays.toString(arr1));
        int []arr2={64,45,15,51,1,5,31};
        paixu2(arr2);
        System.out.println(Arrays.toString(arr2));
        int []arr3={64,45,15,51,1,5,31,88,46,95};
        haset(arr3);
        System.out.println(Arrays.toString(arr3));
    }
}
